package 困难.贪心思想;

import java.util.Arrays;

/**
 * 给你 n 个长方体 cuboids ，其中第 i 个长方体的长宽高表示为 cuboids[i] =
 * [widthi, lengthi, heighti]（下标从 0 开始）。请你从 cuboids 选出一个
 * 子集 ，并将它们堆叠起来。
 * 如果 widthi <= widthj 且 lengthi <= lengthj 且 heighti <= heightj ，
 * 你就可以将长方体 i 堆叠在长方体 j 上。你可以通过旋转把长方体的长宽高重
 * 新排列，以将它放在另一个长方体上。
 * 返回 堆叠长方体 cuboids 可以得到的 最大高度 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/maximum-height-by-stacking-cuboids
 */
public class 堆叠长方体的最大高度_1691 {

    public static void main(String[] args) {

    }

    /**
     * 求的是可以堆叠的最大高度，而长方体可以任意翻转，优先选择
     * 最长的边作为高（证明？？？）
     * dp[i] 表示以 i 长方体作为低的最大长度，那么需要保证
     * 可以堆叠在 i 长方体上面的所有长方体都在 [0,i-1] 的位置
     * 可以根据 w+l+g 排序， wj <= wi 且 lj <= li 且 hj <= hi
     * 可以推断出 wj+lj+hj<=wi+li+hi
     */
    public int maxHeight(int[][] cuboids) {
        for (int i = 0; i < cuboids.length; i++) {
            Arrays.sort(cuboids[i]);
        }
        Arrays.sort(cuboids, (a, b) -> (a[0] + a[1] + a[2]) - (b[0] + b[1] + b[2]));
        int[] dp = new int[cuboids.length];
        int maxHigh = cuboids[0][2];
        dp[0] = cuboids[0][2];

        for (int i = 1; i < cuboids.length; i++) {
            // 只堆叠当前一个长方体的高度
            dp[i] = cuboids[i][2];
            for (int j = 0; j < i; j++) {
                // 前面长方体要比当前小
                if (cuboids[j][0] <= cuboids[i][0] &&
                        cuboids[j][1] <= cuboids[i][1] &&
                        cuboids[j][2] <= cuboids[i][2]) {
                    dp[i] = Math.max(dp[i], dp[j] + cuboids[i][2]);
                }
            }
            maxHigh = Math.max(maxHigh, dp[i]);
        }

        return maxHigh;
    }

}
